package org.ala.tree.bst;

import java.util.Comparator;
import java.util.LinkedList;

import org.ala.tree.AbstractTree;


/**
 * 链表二叉搜索树
 * 
 * @author ala
 * @date 2025年5月16日
 */
public class BSTLinked<K, V> extends AbstractTree<K, V> {

	
	public BSTLinked(Comparator<K> comparator) {
		super(comparator);
	}


	/**
	 * 	根节点
	 */
	protected Node HEAD;

	public int size() {
		return size;
	}


	@Override
	public boolean add(K k, V v) {
		if (size == 0) {
			size++;
			HEAD = new Node(k, v);
			return true;
		}
		if (_add(HEAD, new Node(k, v))) {
			size++;
			return true;
		} else {
			return false;
		}
	}
	protected boolean _add(Node r, Node n) {
		int c = comparator.compare(n.key, r.key);
		if (c == 0) { return false; }
		else if (c < 0) {
			if (r.left == null) { r.left = n; n.parent = r; n.isLeft = true; return true; }
			else { return _add(r.left, n); }
		} else {
			if (r.right == null) { r.right = n; n.parent = r; return true; }
			else { return _add(r.right, n); }
		}
	}


	@Override
	public boolean remove(K k) {
		if (size == 0) { return false; }
		Node n = _search(HEAD, k);
		if (n == null) { return false; }
		
		//	左右都有，拿中序遍历的下一个节点为当前节点
		if (n.left != null && n.right != null) {
			Node nxt = inorderTraversal(k);
			//	nxt原先的父节点断连
			if (nxt.isLeft) {nxt.parent.left = null;}
			else {nxt.parent.right = null;}
			//	nxt的左右针，父针改为n的
			nxt.left = n.left; nxt.right = n.right; nxt.parent = n.parent;
			//	n原先的父节点的左右子节点改为nxt
			if (n.isLeft) {n.parent.left = nxt;}
			else {n.parent.right = nxt;}
		}
		//	如果只有1个节点，直接把子节点提上来
		else if (n.left != null) {
			if (n.isLeft) {n.parent.left = n.left;}
			else {n.parent.right = n.left;}
		} else if (n.right != null) {
			if (n.isLeft) {n.parent.left = n.right;}
			else {n.parent.right = n.right;}
		}
		//	如果左右节点都为空，直接删n
		else {
			if (n.isLeft) {n.parent.left = null;}
			else {n.parent.right = null;}
		}
		size--;
		return true;
	}
	/**
	 * 	中序遍历的下个节点，以及他的父节点
	 */
	protected Node inorderTraversal(K k) {
		Node crt = HEAD;
		LinkedList<Node> stack = new LinkedList<>();
		boolean find = false;
		while (crt != null || !stack.isEmpty()) {
			while (crt != null) {
				stack.addLast(crt);
				crt = crt.left;
			}
			crt = stack.removeLast();
			if (find) {return crt;}
			if (comparator.compare(crt.key, k) == 0) { find = true; }
			
			crt = crt.right;
		}
		return null;
	}



	@Override
	public boolean update(K k, V v) {
		Node node = _search(HEAD, k);
		if (node == null) {return false;}
		node.val = v;
		return true;
	}




	@Override
	public V search(K k) {
		Node n = _search(HEAD, k);
		return n == null ? null : n.val;
	}
	protected Node _search(Node r, K k) {
		if (r == null) {return null;}
		int c = comparator.compare(k, r.key);
		if (c == 0) { return r; }
		else if (c < 0) { return _search(r.left, k); }
		else {return _search(r.right, k);}
	}


	@Override
	public String toString() {
		StringBuilder sbuf = new StringBuilder();
		postOrder(HEAD, 0, sbuf);
		return sbuf.toString();
	}
	protected void postOrder(Node r, int level, StringBuilder sbuf) {
		if (r == null) {return ;}
		StringBuilder t = new StringBuilder();
		for (int l = 0 ; l < level ; l++) {t.append("\t");}
		sbuf.append(t).append(r.val).append(r.isLeft ? " L" : " R").append("\n");
		postOrder(r.left, level+1, sbuf);
		postOrder(r.right, level+1, sbuf);
	}


	public class Node {
		K key;
		V val;
		Node left, right, parent;
		boolean isLeft;
		public Node(K key, V val) {
			this.key = key;
			this.val = val;
		}
	}
}
